class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] person1, int[] person2) {
                if (person1[0] != person2[0]) {
                    return person2[0] - person1[0];
                } else {
                    return person1[1] - person2[1];
                }
            }
        });
        List<int[]> ans = new ArrayList<int[]>();
        for (int[] person : people) {
            ans.add(person[1], person);
        }
        return ans.toArray(new int[ans.size()][]);
    }
}









class Solution {
    public int minAddToMakeValid(String s) {
        int bol=0;
        int sum=0;
        for(int i=0;i<s.length();i++){
            bol+=s.charAt(i)=='('?1:-1;
            if(bol==-1){
                sum++;
                bol++;
            }
        }
        return bol+sum;
    }
}








class Solution {
    public int canBeTypedWords(String text, String brokenLetters) {
        String[] str=text.split(" ");
        Set<Character> buset= new HashSet<>();
        for(int i=0;i<brokenLetters.length();i++){
            buset.add(brokenLetters.charAt(i));
        }
        int count=0;
        boolean bool=true;
        for(String word : str){
            bool=true;
            for(int i=0;i<word.length();i++){
                if(buset.contains(word.charAt(i))){
                    bool=false;
                    break;
                }
            }
            if(bool){
                count++;
            }
        }
        return count;
    }
}











class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len=cost.length;
        int count=0;
        int sum=0;
        for(int i=2;i<len+1;i++){
            int tmp=Math.min(sum+cost[i-2],count+cost[i-1]);
            sum=count;
            count=tmp;
        }
        return count;
    }
}








import java.util.Arrays;

class Solution {
    public int minTimeToType(String word) {
        char a='a';
        int pre=0;
        for(int i=0;i<word.length();i++){
            char ch=word.charAt(i);
            int sum1;
            int sum2;
            if(a<ch){
                sum1=ch-a;
                sum2=a-ch+26;
            }else{
                sum1=a-ch;
                sum2=ch-a+26;
            }
            pre+=Math.min(sum1,sum2)+1;
            a=ch;
        }
        return pre;
    }
}











class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int count=0;
        int sum=0;
        for(int i=satisfaction.length-1;i>=0;i--){
            int tmp=satisfaction[i];
            if(sum+tmp>0){
                sum+=tmp;
                count+=sum;
            }else{
                break;
            }
        }
        return count;
    }
}














class Solution {
    public int minCost(int[][] costs) {
        int a1=costs[0][0];
        int a2=costs[0][1];
        int a3=costs[0][2];
        for(int i=1;i<costs.length;i++){
            int b1=Math.min(a2,a3)+costs[i][0];
            int b2=Math.min(a1,a3)+costs[i][1];
            int b3=Math.min(a1,a2)+costs[i][2];
            a1=b1;
            a2=b2;
            a3=b3;
        }
        return Math.min(Math.min(a1,a2),a3);
    }
}












class Solution {
    public void gameOfLife(int[][] board) {
        int[][] temp = new int[board.length + 2][board[0].length + 2];
        for (int i = 0; i < temp.length; i++) {
            if (i >= 1 && i < temp.length - 1) {
                for (int j = 1; j < temp[i].length - 1; j++) {
                    temp[i][j] = board[i - 1][j - 1];
                }
            } else {
                for (int j = 0; j < temp[i].length; j++) {
                    temp[i][j] = 0;
                }
            }
        }

        for (int i = 1; i < temp.length - 1; i++) {
            for (int j = 1; j < temp[i].length - 1; j++) {
                int aliveCellNumber = 0;
                if (temp[i-1][j-1] == 1) {
                    aliveCellNumber++;
                }
                if (temp[i-1][j] == 1) {
                    aliveCellNumber++;
                }
                if (temp[i-1][j+1] == 1) {
                    aliveCellNumber++;
                }
                if (temp[i][j-1] == 1) {
                    aliveCellNumber++;
                }
                if (temp[i][j+1] == 1) {
                    aliveCellNumber++;
                }
                if (temp[i+1][j-1] == 1) {
                    aliveCellNumber++;
                }
                if (temp[i+1][j] == 1) {
                    aliveCellNumber++;
                }
                if (temp[i+1][j+1] == 1) {
                    aliveCellNumber++;
                }

                if (temp[i][j] == 1) {
                    if (aliveCellNumber < 2 || aliveCellNumber > 3) {
                        board[i-1][j-1] = 0;
                    }
                } else {
                    if (aliveCellNumber == 3) {
                        board[i-1][j-1] = 1;
                    }
                }
            }
        }
    }
}













//class Solution {
//    public int countBattleships(char[][] board) {
//        int count=0;
//        int row=board.length;
//        int col=board[0].length;
//        for(int i=0;i<row;i++){
//            for(int j=0;j<col;j++){
//                if(board[i][j]=='X'){
//                    if((i<=0||board[i-1][j]!='X')&&(j<=0||board[i][j-1]!='X')){
//                        count++;
//                    }
//                }
//            }
//        }
//        return count;
//    }
//}












//class Solution {
//    public int numTeams(int[] rating) {
//        int len=rating.length;
//        int count=0;
//        for(int j=1;j<len-1;j++){
//            int iless=0;
//            int kless=0;
//            int imoer=0;
//            int kmoer=0;
//            for(int i=j-1;i>=0;i--){
//                if(rating[i]<rating[j]){
//                    iless++;
//                }else{
//                    imoer++;
//                }
//            }
//            for(int k=j+1;k<len;k++){
//                if(rating[j]>rating[k]){
//                    kless++;
//                }else{
//                    kmoer++;
//                }
//            }
//            count+=iless*kmoer+kless*imoer;
//        }
//        return count;
//    }
//}










//class Solution {
//    public boolean stoneGame(int[] piles) {
//        int len=piles.length;
//        int[][] arr=new int[len][len];
//        for(int i=0;i<len;i++){
//            arr[i][i]=piles[i];
//        }
//
//        for(int row=len-2;row>=0;row--){
//            for(int col=row+1;col<len;col++){
//                arr[row][col]=Math.max(piles[row]-arr[row+1][col],piles[col]-arr[row][col-1]);
//            }
//        }
//        return arr[0][len-1]>0;
//    }
//}









//class Solution {
//    public int heightChecker(int[] heights) {
//        int[] arr=new int[101];
//        for(int i=0;i<heights.length;i++){
//            arr[heights[i]]++;
//        }
//        int count=0;
//        for(int i=1,j=0;i<arr.length;i++){
//            while(arr[i]-->0){
//                if(heights[j++]!=i){
//                    count++;
//                }
//            }
//        }
//        return count;
//    }
//}